package com.leetcode.algorithm.y22.m05;

import java.util.List;

/**
 * 120. 三角形最小路径和 
 * https://leetcode.cn/problems/triangle/
 * 
 * @author jie.deng
 *
 */
class Question0120Solution01 {

	// DP
	public int minimumTotal(List<List<Integer>> triangle) {
		if (triangle == null || triangle.size() == 0) {
			return 0;
		}

		int rows = triangle.size();
		int maxCols = triangle.get(rows - 1).size();
		// 状态定义：dp[i][j]表示到达三角形第i行第j列的最小路径和
		int[][] dp = new int[rows][maxCols];
		// 初始化
		dp[0][0] = triangle.get(0).get(0);

		for (int i = 1; i < rows; i++) {
			int cols = triangle.get(i).size();
			for (int j = 0; j < cols; j++) {
				// 状态转移方程
				if (j == 0) {
					dp[i][j] = triangle.get(i).get(j) + dp[i - 1][j]; // 没有dp[i - 1][j - 1]
				} else if (j == cols - 1) {
					dp[i][j] = triangle.get(i).get(j) + dp[i - 1][j - 1]; // 没有dp[i - 1][j]
				} else {
					dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
				}
			}
		}

		// 最小值即最后一行的最小值
		int minimumTotal = dp[rows - 1][0];
		for (int colIdx = 1; colIdx < maxCols; colIdx++) {
			minimumTotal = Math.min(minimumTotal, dp[rows - 1][colIdx]);
		}
		return minimumTotal;
	}

}